CSE MENTOR: lab programs

Implement the data link layer framing methods such as character count, character stuffing and bit stuffing

June 04, 2023 CSE MENTORS 0

<p style="text-align: justify;"> <b>Character Count:
</b>In the character count method, the sender includes a count of the 
characters in each frame as a header field. The receiver knows the frame
 length by reading this count and can extract the data accordingly. For 
example, if a frame has the data "HELLO," the sender will add a header 
field with the value "5" to indicate the frame length. The receiver 
reads this count and knows that it needs to extract the next five 
characters as the frame.</p><pre class="brush:Java">#include stdio.h<stdio .h="">
#include string.h<string .h="">

#define MAX_FRAME_SIZE 100

void sendFrame(const char* data) {
    int length = strlen(data);
    printf("Sending frame: %d%s\n", length, data);
}

void receiveFrame(const char* frame) {
    int length = 0;
    sscanf(frame, "%d", <length);
    const char* data = frame + sizeof(int);

printf("Received frame: %d%s\n", length, data);
}

int main() {
    const char* message = "HELLO";

sendFrame(message);

char frame[MAX_FRAME_SIZE];
    sprintf(frame, "%d%s", strlen(message), message);

receiveFrame(frame);

return 0;
}

<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjXyoj6mtZVb3r8979N_7R0KRw-dIdjASAeiembUxvddxchIEqp6Tf5uKWAAxkOWmOhtwD94Inn-e1aA8rtTA-LgeINyJ6wqI8Q3Mqy0t0WSkt6_zgudXmkSC7C88ua4K0_xk2KiyPdRfM7NUYQIkat18Q6S8JKedDzDAgLj6Sf3Le4o1DStXCJXaY/s1482/out1.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="783" data-original-width="1482" height="338" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjXyoj6mtZVb3r8979N_7R0KRw-dIdjASAeiembUxvddxchIEqp6Tf5uKWAAxkOWmOhtwD94Inn-e1aA8rtTA-LgeINyJ6wqI8Q3Mqy0t0WSkt6_zgudXmkSC7C88ua4K0_xk2KiyPdRfM7NUYQIkat18Q6S8JKedDzDAgLj6Sf3Le4o1DStXCJXaY/w640-h338/out1.png" width="640" /></a></div><br /></string></stdio></pre><b>Character Stuffing: </b>Character stuffing is a framing method that allows data frames to contain special characters by adding a delimiter before and after the special characters. The delimiter is a unique character sequence that is not present in the data itself. When the sender encounters a special character in the data, it adds the delimiter before and after the special character. The receiver looks for the delimiter to identify the start and end of each frame and removes the delimiter while extracting the data. This ensures that the special characters within the data do not interfere with the framing process.<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimZCiGi8W23MbsBL8Q8QrMKD6euTALYqR0b2_8NJ6qXetdy5_xST40wM6FCTvQfECDBiTE7ECNCgWyLkPvfVuJc8y7PC3YwAZdvZK1C-NSY-PyHpRXIOjhQh7RZk_RXT2_9qRmVSuTgKd4YOp5_UazDjnsOZwfQCHjztVj7i4K5i5t_PX5YXG9nFaC/s900/wt.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="437" data-original-width="900" height="155" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimZCiGi8W23MbsBL8Q8QrMKD6euTALYqR0b2_8NJ6qXetdy5_xST40wM6FCTvQfECDBiTE7ECNCgWyLkPvfVuJc8y7PC3YwAZdvZK1C-NSY-PyHpRXIOjhQh7RZk_RXT2_9qRmVSuTgKd4YOp5_UazDjnsOZwfQCHjztVj7i4K5i5t_PX5YXG9nFaC/s320/wt.png" width="320" /></a></div><br /><div><br /><div><div><br /></div><div><div>#include <stdio.h></div><div>#include <string.h></div><div><br /></div><div>#define MAX_FRAME_SIZE 100</div><div><br /></div><div>const char FLAG = '#'; // Delimiter character</div><div><br /></div><div>void sendFrame(const char* data) {</div><div>    char stuffedFrame[MAX_FRAME_SIZE * 2]; // Buffer for stuffed frame</div><div>    int index = 0;</div><div><br /></div><div>    stuffedFrame[index++] = FLAG; // Start the frame with the delimiter</div><div><br /></div><div>    for (int i = 0; i < strlen(data); i++) {</div><div>        if (data[i] == FLAG) { // If the character is the delimiter</div><div>            stuffedFrame[index++] = FLAG; // Add an extra delimiter before it</div><div>        }</div><div><br /></div><div>        stuffedFrame[index++] = data[i]; // Add the character to the frame</div><div>    }</div><div><br /></div><div>    stuffedFrame[index++] = FLAG; // End the frame with the delimiter</div><div><br /></div><div>    stuffedFrame[index] = '\0'; // Add null terminator</div><div><br /></div><div>    printf("Sending frame: %s\n", stuffedFrame);</div><div>}</div><div><br /></div><div>void receiveFrame(const char* frame) {</div><div>    char unstuffedFrame[MAX_FRAME_SIZE];</div><div>    int index = 0;</div><div><br /></div><div>    // Skip the first delimiter</div><div>    for (int i = 1; i < strlen(frame) - 1; i++) {</div><div>        if (frame[i] == FLAG && frame[i + 1] == FLAG) {</div><div>            i++; // Skip the extra delimiter</div><div>        }</div><div><br /></div><div>        unstuffedFrame[index++] = frame[i];</div><div>    }</div><div><br /></div><div>    unstuffedFrame[index] = '\0'; // Add null terminator</div><div><br /></div><div>    printf("Received frame: %s\n", unstuffedFrame);</div><div>}</div><div><br /></div><div>int main() {</div><div>    const char* message = "H#ELLO#"; // Message with special characters</div><div><br /></div><div>    sendFrame(message);</div><div><br /></div><div>    receiveFrame("#H##ELLO##");</div><div><br /></div><div>    return 0;</div><div>}</div></div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEikb6m7deP5tl1Kbg6UiJZcz07cSO422SH8eop_p0jC0D1p9xonvwhan0YWKYiI9zcRIG1Phy2BA_x88d2uiiUaEBGctTg2zDlPpygRZfIDfIZu3PJ9UaQ_hcH45ZE8TdZ7R9-JFxDPP1qKZiTtcH-fF1KQ6i7eJtAf0MtlWAAhFu4SbuNoo5KJvX2u/s1481/out2.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="782" data-original-width="1481" height="338" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEikb6m7deP5tl1Kbg6UiJZcz07cSO422SH8eop_p0jC0D1p9xonvwhan0YWKYiI9zcRIG1Phy2BA_x88d2uiiUaEBGctTg2zDlPpygRZfIDfIZu3PJ9UaQ_hcH45ZE8TdZ7R9-JFxDPP1qKZiTtcH-fF1KQ6i7eJtAf0MtlWAAhFu4SbuNoo5KJvX2u/w640-h338/out2.png" width="640" /></a></div><br /><div><br /></div><div style="text-align: justify;">Bit stuffing is a framing method that operates at the bit level. It 
involves adding extra bits to the data to ensure that a specific bit 
pattern does not appear within the frame, except as a delimiter. The 
most common use of bit stuffing is the HDLC (High-Level Data Link 
Control) protocol. In bit stuffing, a predefined bit pattern (known as 
the flag) is used as the frame delimiter. Whenever the sender encounters
 the flag pattern in the data, it adds an extra bit (0) after five 
consecutive 1s. The receiver reads the data and removes the extra 0 
after five consecutive 1s while extracting the frame. This ensures that 
the flag pattern appears only as a delimiter and not within the data.</div><div style="text-align: justify;"><div>#include <stdio.h></div><div>#include <string.h></div><div><br /></div><div>#define MAX_FRAME_SIZE 100</div><div><br /></div><div>const char FLAG = '0'; // Flag bit pattern</div><div>const int MAX_CONSECUTIVE_ONES = 5; // Maximum consecutive ones before stuffing</div><div><br /></div><div>void sendFrame(const char* data) {</div><div>    char stuffedFrame[MAX_FRAME_SIZE * 2]; // Buffer for stuffed frame</div><div>    int index = 0;</div><div>    int consecutiveOnes = 0;</div><div><br /></div><div>    stuffedFrame[index++] = FLAG; // Start the frame with the flag pattern</div><div><br /></div><div>    for (int i = 0; i < strlen(data); i++) {</div><div>        if (data[i] == '1') {</div><div>            consecutiveOnes++; // Count consecutive ones</div><div>        }</div><div>        else {</div><div>            consecutiveOnes = 0; // Reset consecutive ones counter</div><div>        }</div><div><br /></div><div>        stuffedFrame[index++] = data[i]; // Add the bit to the frame</div><div><br /></div><div>        if (consecutiveOnes == MAX_CONSECUTIVE_ONES) {</div><div>            stuffedFrame[index++] = '0'; // Stuff a zero bit</div><div>            consecutiveOnes = 0; // Reset consecutive ones counter</div><div>        }</div><div>    }</div><div><br /></div><div>    stuffedFrame[index++] = FLAG; // End the frame with the flag pattern</div><div><br /></div><div>    stuffedFrame[index] = '\0'; // Add null terminator</div><div><br /></div><div>    printf("Sending frame: %s\n", stuffedFrame);</div><div>}</div><div><br /></div><div>void receiveFrame(const char* frame) {</div><div>    char unstuffedFrame[MAX_FRAME_SIZE];</div><div>    int index = 0;</div><div>    int consecutiveOnes = 0;</div><div><br /></div><div>    // Skip the first flag pattern</div><div>    for (int i = 1; i < strlen(frame) - 1; i++) {</div><div>        unstuffedFrame[index++] = frame[i]; // Add the bit to the unstuffed frame</div><div><br /></div><div>        if (frame[i] == '1') {</div><div>            consecutiveOnes++; // Count consecutive ones</div><div>        }</div><div>        else {</div><div>            consecutiveOnes = 0; // Reset consecutive ones counter</div><div>        }</div><div><br /></div><div>        if (consecutiveOnes == MAX_CONSECUTIVE_ONES && frame[i + 1] == '0') {</div><div>            i++; // Skip the stuffed zero bit</div><div>            consecutiveOnes = 0; // Reset consecutive ones counter</div><div>        }</div><div>    }</div><div><br /></div><div>    unstuffedFrame[index] = '\0'; // Add null terminator</div><div><br /></div><div>    printf("Received frame: %s\n", unstuffedFrame);</div><div>}</div><div><br /></div><div>int main() {</div><div>    const char* message = "110111110"; // Message with bit stuffing</div><div><br /></div><div>    sendFrame(message);</div><div><br /></div><div>    receiveFrame("011011110100111101110"); // Received frame with stuffed zero bit</div><div><br /></div><div>    return 0;</div><div>}</div><div><br /></div></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2912C2mgfJNrSaEcWFiX_BzeJV_kbz1E0XaVfp_yJrNdc-pgRCudPna1K7QuxTTd9irGx4VIoB1UhGbPq3UY_MvG2yO9V78_iTXsG5fz_8fzSgEI5vCbIawbxNzmnynRPjbRAsmKh21XhPWiaCLFVx3fsP-TLH31ZR4VzSwZlcudLcJcw3uuiBkhZ/s1478/out3.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="787" data-original-width="1478" height="340" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2912C2mgfJNrSaEcWFiX_BzeJV_kbz1E0XaVfp_yJrNdc-pgRCudPna1K7QuxTTd9irGx4VIoB1UhGbPq3UY_MvG2yO9V78_iTXsG5fz_8fzSgEI5vCbIawbxNzmnynRPjbRAsmKh21XhPWiaCLFVx3fsP-TLH31ZR4VzSwZlcudLcJcw3uuiBkhZ/w640-h340/out3.png" width="640" /></a></div><br /><div style="text-align: justify;"><br /></div><div>If you get any error in above programs, please comment below </div></div></div>

lab programs Implement the data link layer framing methods such as character count, character stuffing and bit stuffing

Character Count: In the character count method, the sender includes a count of the characters in each frame as a header field. The receiv...

NEC CSE 3-1 R20 CN and OS Lab Programs Answers

June 04, 2023 CSE MENTORS 0

<p><b>COURSE OBJECTIVES:</b></p><p></p><ul style="text-align: left;"><li> To understand the Concept of Data link layer framing Methods and different CRC Polynomials.</li><li> Identify the purpose of Scheduling Algorithms, page replacements and Deadlock Algorithm.</li></ul><p></p><p><b>COURSE OUTCOMES:</b></p><p>After successful completion of this course, the students will be able to:</p><p><b>CO 1:</b> Implement routing algorithms.</p><p><b>CO 2:</b> Do the error checking by using CRC polynomials.</p><p><b>CO 3:</b> Solve the experiments on scheduling Algorithms and page replacement algorithms.</p><p><b>CO 4:</b> Handle the deadlocks, like prevention and detection.</p><p><b>List of Experiments in CN</b></p><p>1. Implement the data link layer framing methods such as character count, character stuffing and bit stuffing</p><p>2 Implement on a data set of characters the three CRC polynomials CRC 12, CRC 16 and CRC CCIP</p><p>3 Implement Dijkstra’s algorithm to compute the shortest path through a graph</p><p>4 Take an example subnet graph with weights indicating delay between nodes</p><p>5 Now obtain Routing table art each node using distance vector routing algorithm</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimZCiGi8W23MbsBL8Q8QrMKD6euTALYqR0b2_8NJ6qXetdy5_xST40wM6FCTvQfECDBiTE7ECNCgWyLkPvfVuJc8y7PC3YwAZdvZK1C-NSY-PyHpRXIOjhQh7RZk_RXT2_9qRmVSuTgKd4YOp5_UazDjnsOZwfQCHjztVj7i4K5i5t_PX5YXG9nFaC/s900/wt.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="437" data-original-width="900" height="155" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimZCiGi8W23MbsBL8Q8QrMKD6euTALYqR0b2_8NJ6qXetdy5_xST40wM6FCTvQfECDBiTE7ECNCgWyLkPvfVuJc8y7PC3YwAZdvZK1C-NSY-PyHpRXIOjhQh7RZk_RXT2_9qRmVSuTgKd4YOp5_UazDjnsOZwfQCHjztVj7i4K5i5t_PX5YXG9nFaC/s320/wt.png" width="320" /></a></div><br /><p><br /></p><p><b>List of Experiments in OS</b></p><p>1 Simulate the following CPU scheduling algorithm</p><p>a) FCFS b) SJF c) Round Robin d) Priority</p><p>2 Simulate all page replacement algorithms</p><p>a) FIFO b) LRU c)OPTIMAL</p><p>3 Simulate all file organization techniques</p><p>a) Single level b)Two level</p><p>4 Simulate Bankers Algorithm for Deadlock Avoidance</p>

lab programs Syllabus NEC CSE 3-1 R20 CN and OS Lab Programs Answers

COURSE OBJECTIVES: To understand the Concept of Data link layer framing Methods and different CRC Polynomials. Identify the purpose of Sch...

NEC CSE 3-1 R20 DAA and CD Lab Program Answers

June 04, 2023 CSE MENTORS 0

<p>The course should enable the students to:</p><p></p><ul style="text-align: left;"><li> Learn how to analyze a problem and design the solution for the problem.</li><li>Identify and apply the suitable algorithm for the given real world problem.</li></ul><p></p><p><b>COURSE OUTCOMES:</b></p><p>After successful completion of this course, the students will be able to:</p><p><b>CO 1: </b>Develop programs for searching a given set of element and analyze its time complexity.</p><p><b>CO 2: </b>Implement and analyze the complexity using dynamic algorithms.</p><p><b>CO 3</b>: Solve and analyze the tree traversal techniques.</p><p><b>CO 4:</b> Demonstrate and Develop Lexical Analyzer for a given language.[K3]</p><p><b>CO 5: </b>Develop various bottom up parsers for a given language.[K3]</p><p><b>LIST OF PROGRAMS</b></p><p><b>DAA Programs </b></p><p>1. Write a program to perform Binary Search.</p><p>2. Write a program to find Optimal solution for a Knap Sack Problem using Greedy Method.</p><p>3. Write a program to find Adjacency matrix for a given graph.</p><p>4. Write a program to implement Depth First Search.</p><p>5. Write a program to implement Breadth First Search.</p><p>6. Write a program to find minimum cost of spanning tree using Prims Algorithm.</p><p>7. Write a program to implement Dijkstras algorithm</p><p>8. Write a program to perform All pairs shortest path problem</p><p>9. Write a program to perform Matrix Chain Multiplication</p><p>10. Write a program to solve Eight Queens problem using Back Tracking Technique.</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimZCiGi8W23MbsBL8Q8QrMKD6euTALYqR0b2_8NJ6qXetdy5_xST40wM6FCTvQfECDBiTE7ECNCgWyLkPvfVuJc8y7PC3YwAZdvZK1C-NSY-PyHpRXIOjhQh7RZk_RXT2_9qRmVSuTgKd4YOp5_UazDjnsOZwfQCHjztVj7i4K5i5t_PX5YXG9nFaC/s900/wt.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="437" data-original-width="900" height="155" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimZCiGi8W23MbsBL8Q8QrMKD6euTALYqR0b2_8NJ6qXetdy5_xST40wM6FCTvQfECDBiTE7ECNCgWyLkPvfVuJc8y7PC3YwAZdvZK1C-NSY-PyHpRXIOjhQh7RZk_RXT2_9qRmVSuTgKd4YOp5_UazDjnsOZwfQCHjztVj7i4K5i5t_PX5YXG9nFaC/s320/wt.png" width="320" /></a></div><br /><p><br /></p><p><b>CD Programs</b></p><p>11. Write a Program to Tokenizing a file using C</p><p>12. Write a program to Design a lexical analyzer for given language which should ignore redundant spaces, tabs, new lines and comments.</p><p>13.Write a program to build lexical analyzer. Using Lex tool</p><p>14. Develop functions to find FIRST and FOLLOW of all the variables.</p><p>15. Develop an operator precedence parser for a given language.</p><p>16. Write a program to Build shift reduce parsing algorithm.</p><p>17. Write a program to design an LALR bottom up parser for the given language</p>

lab programs Syllabus NEC CSE 3-1 R20 DAA and CD Lab Program Answers

The course should enable the students to: Learn how to analyze a problem and design the solution for the problem. Identify and apply the su...

Write a program to perform Binary Search using C

May 17, 2023 CSE MENTORS 0

<p> Binary search is a widely used searching algorithm that is efficient for finding a target value in a sorted array or list. It follows a divide-and-conquer approach by repeatedly dividing the search space in half until the target value is found or determined to be absent.</p><div class="flex flex-grow flex-col gap-3"><div class="min-h-[20px] flex flex-col items-start gap-4 whitespace-pre-wrap break-words"><div class="markdown prose w-full break-words dark:prose-invert light"><p>Here's how binary search works:</p><ol><li>Start with a sorted array or list.</li><li>Set the lower bound (start) and upper bound (end) of the search space to the first and last elements of the array, respectively.</li><li>Calculate the middle index of the search space using the formula: <code>mid = (start + end) / 2</code>.</li><li>Compare the middle element with the target value:<ul><li>If the middle element is equal to the target value, the search is successful, and the index is returned.</li><li>If the middle element is greater than the target value, the search space is reduced to the lower half of the array. Set the new upper bound (end) to <code>mid - 1</code> and repeat step 3.</li><li>If the middle element is less than the target value, the search space is reduced to the upper half of the array. Set the new lower bound (start) to <code>mid + 1</code> and repeat step 3.</li></ul></li><li>Repeat steps 3 to 4 until the target value is found or the search space is empty (i.e., <code>start</code> becomes greater than <code>end</code>).</li><li>If the target value is not found, return a "not found" indication.</li></ol><p>Binary search has a time complexity of O(log n), where n is the number of elements in the array. This makes it very efficient compared to linear search, which has a time complexity of O(n) in the worst case. However, binary search requires the array to be sorted beforehand, which can add an additional overhead if the array is frequently modified.</p><p><b>Algorithm </b></p>
  <pre class="brush:Java">def binary_search(arr, target):
    start = 0
    end = len(arr) - 1

while start <= end:
        mid = (start + end) // 2

if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            start = mid + 1
        else:
            end = mid - 1

return -1  # Target value not found

# Example usage:
array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_value = 23

result = binary_search(array, target_value)

if result != -1:
    print(f"Target value {target_value} found at index {result}.")
else:
    print("Target value not found in the array.")
</pre><p><b>Program </b></p>
<pre class="brush:Java">/* Program to Search an Element using BInary Search */

#include <stdio .h="">
/* Function Prototype Declaration */
void binary_search();

/* Global Declaration of Variables */
int a[50], n, item, loc, beg, mid, end, i;

/* We used main() because it's a C-Compiler.
   Use void main() or int main() if necessary  */

main()
{
    printf("\nEnter size of an array: ");
    scanf("%d", &n); // Reading Size of an Array.

printf("\nEnter elements of an array in sorted form:\n");
    for(i=0; i<n; i++)
        scanf("%d", &a[i]);  //Read Array values one by one.

printf("\nEnter ITEM to be searched: ");
    scanf("%d", &item);

/* Calling Function - No Arguments Passing */
    binary_search();    
}
void binary_search()  //called Function - Dont Return Anything.
{
    /* Binary Search Logic */
    
    beg = 0;
    end = n-1;
    mid = (beg + end) / 2;
    while ((beg&lt=end) && (a[mid]!=item))
    {
        if (item &lt a[mid])
            end = mid - 1;
        else
            beg = mid + 1;
        mid = (beg + end) / 2;
    }
    if (a[mid] == item)
        printf("\n\nITEM found at location %d", mid+1);
    else
        printf("\n\nITEM doesn't exist");
}

Output:</stdio></pre></div></div></div><pre style="background: rgb(236, 239, 243); border-radius: 0.25rem; border: 1px solid rgb(224, 224, 229); box-sizing: inherit; font-family: menlo, monaco, monospace; font-size: 0.9rem; line-height: 1.15; margin-bottom: 2rem; margin-top: 2rem; overflow: auto; padding: 1rem;">Enter size of an array: 6

Enter elements of an array in sorted form:
10 20 30 40 50 60

Enter ITEM to be searched: 30

ITEM found at location 3</pre>

lab programs Write a program to perform Binary Search using C

Binary search is a widely used searching algorithm that is efficient for finding a target value in a sorted array or list. It follows a div...